\documentclass[submission]{FPSAC2017}

\articlenumber{57}
\addbibresource{57_Niese.bib}

\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{color}
\usepackage{tikz,pgfplots}
%% Theorem definitions

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
 \theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
 
\DeclareMathOperator{\dg}{dg}
\DeclareMathOperator{\SYT}{SYT}
\DeclareMathOperator{\SSYT}{SSYT}
\DeclareMathOperator{\wt}{wt}
\DeclareMathOperator{\SSYCT}{SSYCT}
\DeclareMathOperator{\SSYRT}{SSYRT}
%%% tableau macros %%%

\newlength\cellsize \setlength\cellsize{15\unitlength}
\savebox2{%
\begin{picture}(15,15)
\put(0,0){\line(1,0){15}}
\put(0,0){\line(0,1){15}}
\put(15,0){\line(0,1){15}}
\put(0,15){\line(1,0){15}}
\end{picture}}
\newcommand\cellify[1]{\def\thearg{#1}\def\nothing{}%
\ifx\thearg\nothing
\vrule width0pt height\cellsize depth0pt\else
\hbox to 0pt{\usebox2\hss}\fi%
\vbox to 15\unitlength{
\vss
\hbox to 15\unitlength{\hss$#1$\hss}
\vss}}
\newcommand\tableau[1]{\vtop{\let\\=\cr
\setlength\baselineskip{-16000pt}
\setlength\lineskiplimit{16000pt}
\setlength\lineskip{0pt}
\halign{&\cellify{##}\cr#1\crcr}}}
\savebox3{%
\begin{picture}(15,15)
\put(0,0){\line(1,0){15}}
\put(0,0){\line(0,1){15}}
\put(15,0){\line(0,1){15}}
\put(0,15){\line(1,0){15}}
\end{picture}}
\newcommand\expath[1]{%
\hbox to 0pt{\usebox3\hss}%
\vbox to 15\unitlength{
\vss
\hbox to 15\unitlength{\hss$#1$\hss}
\vss}}

%%%%% end tableaux macros %%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{lipsum}

\title[Remmel-Whitney rule]{A Remmel-Whitney rule for quasisymmetric Schur functions}

\author {Elizabeth Niese}

\address{Department of Mathematics, Marshall University, Huntington, WV 25755\\}

\received{\today}

\abstract{Remmel and Whitney provided an algorithmic procedure for determining the Littlewood-Richardson coefficients that appear in the Schur function expansion of a product of Schur functions.  Haglund et al. introduced the quasisymmetric Schur functions as a basis for $QSym$.  This paper adapts Remmel and Whitney's approach in order to determine the coefficients that appear in the quasisymmetric Schur function expansion of the product of a quasisymmetric Schur function and a (symmetric) Schur function.}

\resume{Remmel et Whitney ont fourni une proc\'{e}dure algorithmique pour d\'{e}terminer les coefficients de Littlewood-Richardson qui apparaissent dans l'expansion de fonction de Schur d'un produit de fonctions de Schur. Haglund et al. a introduit les fonctions de Schur quasi-sym\'{e}triques comme base de $ QSym $. Cet article adapte l'approche de Remmel et Whitney afin de d\'{e}terminer les coefficients qui apparaissent dans l'expansion de la fonction de Schur quasi-sym\'{e}trique du produit d'une fonction de Schur quasi-sym\'{e}trique et d'une fonction de Schur.}

\keywords{quasisymmetric function, Schur function, Littlewood-Richardson rule}


\begin{document}

\maketitle

\section{Introduction}\label{sec:intro}

The Littlewood-Richardson rule for computing the coefficients of the Schur functions appearing in the Schur expansion of the product of two Schur functions is a classical result in algebraic combinatorics.  The traditional definition of the Littlewood-Richardson coefficients is the number of skew tableaux of a given content whose reading word is a lattice word.  In ~\cite{RemWhi} a set of standard Young tableaux is defined which can be used to compute the Littlewood-Richardson coefficients that arise in the Schur expansion of the product of two Schur functions.  The set $\mathcal{O}(\lambda*\mu)$ described in~\cite{RemWhi} can be generated by creating a tree of tableaux with certain properties where the leaves of the tree are precisely the elements in $\mathcal{O}(\lambda*\mu)$.  

Recently several quasisymmetric analogues of the Schur functions have been introduced~\cite{HLMvW09,MasRem10}.  These quasisymmetric Schur functions are a refinement of the Schur function and have many properties similar to Schur functions.  However, the product of two quasisymmetric Schur functions does not generally expand positively in the quasisymmetric Schur basis.  The purpose of this paper is to extend the Remmel-Whitney rule to the product of a quasisymmetric Schur function and a (symmetric) Schur function.  This product does expand positively in the quasisymmetric Schur basis and has Littlewood-Richardson coefficients that count analogous objects to those in the symmetric setting, however, the Littlewood-Richardson composition tableaux are difficult to construct, with several conditions on the reading word and relative ordering of entries in triples of cells \cite{ferRS, HLMvW10}.  Thus, this Remmel-Whitney rule is more straightforward to use when computing products.  A special case of this rule, $\mathcal{CS}_\alpha\cdot s_{(1)}$, was established in~\cite{and-thesis}.  Future work will involve extending the rule to products of two quasisymmetric Schur functions.

 
 \section{Background}\label{sec:back}
In this paper we use the traditional (symmetric) Schur functions, the column-strict Young quasisymmetric Schur functions, and the row-strict Young quasisymmetric Schur functions.  For a full treatment of the properties of quasisymmetric Schur functions see \cite{ferRS,HLMvW09,HLMvW10,MN-SkewRS}.  Here we give the combinatorial definitions and a brief overview of each function.

\subsection{Partitions and Schur functions}
Let $n$ be a positive integer.  Then $\lambda=(\lambda_1,\ldots,\lambda_k)$ is a partition of $n$, denoted $\lambda \vdash n$ if $\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_k>0$ and $\sum_i \lambda_i = n$.  The diagram of $\lambda$, denoted $\dg(\lambda)$, is the collection of left-justified boxes with $\lambda_i$ boxes in row $i$, where row $1$ is the bottom row, following the French convention.  A semi-standard Young tableau (SSYT) of shape $\lambda$ is a placement of positive integers in $\dg(\lambda)$ that is weakly increasing left to right along rows and strictly increasing up columns as seen in \cref{fig:ssyt}.  The {\em content monomial} of a semi-standard Young tableau $T$ is $x^T=\prod_i x_i^{c_i}$ where $c_i$ is the number of times $i$ appears in $T$.  Let $\SSYT(\lambda)$ denote the set of all semi-standard Young tableaux of shape $\lambda$.  We can now define the Schur functions, $s_\lambda$, by 
\[s_\lambda = \sum_{T \in \SSYT(\lambda)}x^T.\]

\begin{figure}
\[T=\tableau{3\\2&2&3&4\\1&1&1&2&2&4}\]
\caption{A semi-standard tableau of shape $(6,4,1)$ with content monomial $x^T=x_1^3x_2^4x_3^2x_4^2$.}\label{fig:ssyt}
\end{figure}
 
For example, restricting to the variables $x_1,x_2,x_3$, we can compute $s_{(2,1)}(x_1,x_2,x_3) = x_1^2x_2+x_1x_2^2+x_1^2x_3+x_1x_3^2+x_2^2x_3+x_2x_3^2+2x_1x_2x_3. $


\subsection{Compositions and quasisymmetric Schur functions}

Given a positive integer $n$, a {\em (strong) composition} of $n$ is a sequence $\alpha = (\alpha_1,\alpha_2,\ldots,\alpha_k)$ with $\alpha_i>0$ for all $i$ and $\sum_i \alpha_i = n$.  A {\em weak composition} allows for parts of size 0.  As with partitions, the diagram of $\alpha$, denoted $\dg(\alpha)$, is the collection of left-justified boxes with $\alpha_i$ boxes in row $i$, the $i$th row from the bottom, in the French convention.  

A filling $T$ of the diagram of $\alpha$ is a {\em semi-standard Young (column-strict) composition tableau} (SSYCT) of shape $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_n)$ if
\begin{enumerate}
\item the first column of $T$ is strictly increasing from bottom to top,
\item each row of $T$ weakly increases from left to right, and
\item $T$ satisfies the {\em column-strict triple rule:}  Let $m = \max\{\alpha_i\}$.  Then for all $1\leq i<j\leq n$ and $1\leq k <m$, if $T(i,k+1)\neq \infty$ and $T(i,k+1)\geq T(j,k)$, then $T(i,k+1)>T(j,k+1)$, assuming the entry in any cell not in $\alpha$ is $\infty$.  Note that $T(i,k)$ indicates the entry in the $i$th row and $k$th column of $\alpha$.
\end{enumerate}
Denote the set of semi-standard composition tableaux of shape $\alpha$ by $\SSYCT(\alpha)$.  Then the {\em Young quasisymmetric Schur function} is defined 
\[\mathcal{CS}_\alpha = \sum_{T\in \SSYCT(\alpha)}x^T.\]
The semi-standard composition tableaux in \cref{fig:SSYCT} yields $\mathcal{CS}_{(1,2,2)}(x_1,x_2,x_3,x_4) = x_1x_2^2x_3^2+x_1x_2x_3^2x_4+x_1x_2^2x_3x_4+x_1x_2^2x_4^2+x_1x_2x_3x_4^2+x_1x_3^2x_4^2+x_2x_3^2x_4^2.$
\begin{figure}
\[\tableau{3&3\\2&2\\1}\quad \tableau{3&3\\2&4\\1} \quad \tableau{3&4\\2&2\\1} \quad \tableau{4&4\\2&2\\1} \quad \tableau{4&4\\2&3\\1}\quad \tableau{4&4\\3&3\\1}\quad \tableau{4&4\\3&3\\2}\]
\caption{The elements in $\SSYCT((1,2,2))$ restricted to entries from $\{1,2,3,4\}$.}\label{fig:SSYCT}
\end{figure}



Similarly, a filling $F$ of the diagram of $\alpha$ is a {\em semi-standard Young row-strict composition tableau} (SSYRT) of shape $\alpha = (\alpha_1,\alpha_2,\ldots,\alpha_n)$ if 
\begin{enumerate}
\item the first column of $F$ is weakly increasing from bottom to top,
\item each row of $F$ strictly increases from left to right, and
\item $F$ satisfies the {\em row-strict triple rule:}  Let $m=\max\{\alpha_i\}$.  Then for all $1\leq i<j\leq n$ and $1\leq k<m$, if $T(i,k+1)\neq \infty$ and $T(i,k+1)>T(j,k)$, then $T(i,k+1)\geq T(j,k+1)$, assuming the entry in any cell not in $\alpha$ is $\infty$.
\end{enumerate}
Denote the set of semi-standard row-strict composition tableaux of shape $\alpha$ by $\SSYRT(\alpha)$.  The the {\em Young row-strict quasisymmetric Schur function} is defined
\[\mathcal{RS}_\alpha = \sum_{F\in \SSYRT(\alpha)}x^F.\]
From the SSYRT in \cref{fig:SSYRT} we see that 
\begin{align*}\mathcal{RS}_{(1,2,1)}&(x_1,x_2,x_3,x_4) = x_1x_2x_3^2+x_2^2x_3^2+x_1x_2x_3x_4+x_1x_2x_4^2+x_2^2x_3x_4+x_2^2x_4^2\\
&+x_1^2x_2x_3+x_1^2x_3^2+x_1^2x_2x_4+ x_1^2x_3x_4+x_1^2x_4^2+x_1x_3x_4^2+x_2x_3x_4^2+x_3^2x_4^2+x_1^2x_2^2.
\end{align*}
\begin{figure}
\[\tableau{3\\2&3\\1}\quad \tableau{3\\2&3\\2}\quad \tableau{4\\2&3\\1}\quad \tableau{4\\2&4\\1}\quad \tableau{4\\2&3\\2}\quad \tableau{4\\2&4\\2} \quad \tableau{3\\1&2\\1}\]\[ \tableau{3\\1&3\\1}\quad \tableau{4\\1&2\\1}\quad \tableau{4\\1&3\\1}\quad\tableau{4\\1&4\\1}\quad \tableau{4\\3&4\\1}\quad \tableau{4\\3&4\\2}\quad \tableau{4\\3&4\\3}\quad \tableau{2\\1&2\\1}\]
\caption{The elements in $\SSYRT((1,2,1))$ restricted to entries from $\{1,2,3,4\}$.}\label{fig:SSYRT}
\end{figure}

Both the Young quasisymmetric Schur functions and the Young row-strict quasisymmetric Schur functions refine the Schur functions \cite{HLMvW09,MN-SkewRS,MasRem10}.  That is, 
\[s_\lambda = \sum_{\alpha:\boldsymbol{\lambda}(\alpha)=\lambda}\mathcal{CS}_\alpha=\sum_{\beta:\boldsymbol{\lambda}(\beta)=\lambda'}\mathcal{RS}_\beta\] where $\boldsymbol{\lambda}(\alpha)$ denotes the partition obtained by listing the parts of $\alpha$ in weakly decreasing order. 

\section{Littlewood-Richardson rules}\label{sec:LR}

Since both the Young quasisymmetric Schur functions and Young row-strict quasisymmetric Schur functions provide a basis for the vector space of quasisymmetric function \cite{HLMvW09,MN-SkewRS}, it is natural to want a quasisymmetric analogue of the Littlewood-Richardson rule for the product of two Schur functions.  While a combinatorial rule for the product of two quasisymmetric Schur functions has remained elusive, a rule for the product of a quasisymmetric Schur function and a (symmetric) Schur function exists for both types of quasisymmetric Schur functions.  We briefly outline these rules and refer the reader to \cite{ferRS,HLMvW10, MN-SkewRS} for a more comprehensive treatment.


We start by rewriting the Littlewood-Richardson rule for quasisymmetric Schur functions given in \cite{HLMvW10} for reverse composition tableaux in our context for semi-standard Young composition tableaux.
\begin{figure}
\[\tableau{{}&{}\\*&*&{}&{}\\*&{}\\{}&{}\\*&*&{}}\qquad \tableau{*&*\\{}&{}&{}&{}\\*&{}\\{}&{}\\*&*&{}}\qquad \tableau{*&*\\*&{}&{}&{}\\{}&{}\\*&*\\{}&{}&{}}\]
\caption{Diagrams of shape $(3,2,2,4,2)/(2,1,2)$ with removed cells indicated by~$*$. }\label{fig:gamma}
\end{figure}

\begin{definition}\label{def:LRCol} Given compositions $\alpha, \beta$,  let $\gamma$ be a weak composition such that $\gamma_i\leq \beta_i$ for each part of $\gamma$ and $\gamma^+=\alpha$ where $\gamma^+$ is $\gamma$ with all zero parts removed.  Then a skew composition diagram of shape $\beta//\gamma$ is said to be of shape $\beta/\alpha$.  More than one $\gamma$ may satisfy this requirement as seen in \cref{fig:gamma}.  A tableau $V$ of shape $\beta/\alpha$ is a {\em Littlewood-Richardson composition tableau} when 

\begin{enumerate}
\item The cells in $\alpha$ are filled with zeros, as is an additional column, column 0, to the left of the first column of $\beta$.  Where there are multiple 0's in the same column, we consider the 0's to be increasing from top to bottom.
\item A triple of cells in rows $i$ and $j$, $i<j$, is a {\em Type A triple} if $\beta_i\leq \beta_j$ with the cells arranged as shown in \cref{fig:abtriples}, and is a {\em Type B triple} if $\beta_i>\beta_j$ with the cells arranged as shown in \cref{fig:abtriples}.  All Type A and B triples are {\em inversion triples}, meaning $c\leq b <a$ or $a<c\leq b$.  Note that this condition implies each row is weakly increasing from left to right.
 \item The {\em column reading word} $w_{col}(T)$ obtained by reading down each column of $V$ starting with the rightmost column (omitting all 0's) must be a {\em lattice word}, a word $w_1w_2\ldots w_n$ where, for each $i<\ell(\mu)$ and each prefix $w_1w_2\ldots w_j$ with $j\leq n$ the number of $i$'s in the prefix is weakly greater than the number of $i+1$'s in the prefix.
\end{enumerate}
\end{definition}
\begin{figure}
\begin{center}
\begin{tabular}{cc}
${\displaystyle\tableau{c&b\\\\&a}}$ \hspace{.3in}&\hspace{.3in} ${\displaystyle \tableau{a\\\\c&b}}$\\\\
Type A \hspace{.3in}&\hspace{.3in} Type B
\end{tabular}
\end{center}
\caption{The two types of triples between rows $i$ and $j$, $i<j$, in a tableau of shape $\beta$.  When $\beta_i\leq \beta_j$ consider Type A triples.  When $\beta_i>\beta_j$ consider Type B triples.}\label{fig:abtriples}
\end{figure}
We denote by $LR(\beta/\alpha, \lambda)$ the set of Littlewood-Richardson composition tableaux of shape $\beta/\alpha$ with content $\lambda$.  and let $B_{\alpha,\lambda}^\beta = |LR(\beta/\alpha,\lambda)|$.

\begin{theorem}[\cite{HLMvW10}]\label{thm:cslr}
Let $\lambda$ be a partition and $\alpha$ a composition.  Then 
\[\mathcal{CS}_\alpha \cdot s_\lambda = \sum_{\beta} B_{\alpha,\lambda}^\beta \mathcal{CS}_\beta\] where the sum is over all compositions $\beta$ such that $|\beta/\alpha|=|\lambda|$.
\end{theorem}


The rule for Young row-strict quasisymmetric Schur functions is similar, but the column reading word is formed by reading up each column starting with the leftmost column.  The triple rule is also adjusted to accommodate the row-strict condition.

\begin{definition}\label{def:rslrrule}
Let $\alpha$ and $\beta$ be compositions.  A {\em Littlewood-Richardson skew row-strict composition tableau} $F$ of shape $\beta/\alpha$ is a filling of a diagram of shape $\beta//\gamma$ where $\gamma$ is a weak composition with $\gamma\subseteq \beta$ and $\gamma^+=\alpha$, such that
\begin{enumerate}
\item The cells in $\gamma$ are filled with 0's, and there is a column 0 which is also filled with 0's.  We consider 0's to strictly increase across rows left to right.
\item Each triple (type A or B) must satisfy $c<b\leq a$ or $a\leq c<b$, including triples containing cells in column 0.  Note that satisfying the triple condition implies the rows of $F$ are strictly increasing (omitting 0's).
\item The row-strict column reading word, $rw_{col}(F)$, obtained by reading up each column, omitting 0's, starting with the leftmost column, is a lattice word with content $\lambda$.
\end{enumerate}
Denote the set of all such tableaux by $RSLR(\beta/\alpha,\lambda)$ and let $D_{\alpha,\lambda}^\beta = |RSLR(\beta/\alpha,\lambda)|$.
\end{definition}

\begin{theorem}[\cite{MN-SkewRS}] \label{thm:rslr}Let $\lambda$ be a partition and $\alpha$ a composition.  Then 
\[\mathcal{RS}_\alpha \cdot s_\lambda = \sum_{\beta} D_{\alpha,\lambda}^\beta \mathcal{RS}_\beta\] 
where the sum is over all compositions $\beta$ such that $|\beta/\alpha|=|\lambda|$.\end{theorem}

\section{Remmel-Whitney rules}

For both types of quasisymmetric Schur functions a special composition tableau will figure prominently in the statement of the Remmel-Whitney rules.
\begin{definition}\label{def:Salpha}
Let $\alpha=(\alpha_1,\ldots,\alpha_k)$ be a (strong) composition and $\lambda=(\lambda_1,\ldots,\lambda_m)$ be a partition.  Then define $\alpha*\lambda:=(\lambda_1+\alpha_1,\lambda_1+\alpha_2,\ldots, \lambda_1+\alpha_k, \lambda_1,\lambda_2,\ldots, \lambda_m)/(\lambda_1)^k$ and define $S_{\alpha*\lambda}$ to be the filling of $\alpha*\lambda$ obtained by placing the labels $1,2,\ldots, |\alpha|+|\lambda|$ into the diagram of $\alpha*\lambda$ in {\em reverse reading order}, that is, from right to left across rows starting with the bottom row as seen in \cref{fig:Salpha}.  
\end{definition}
 \begin{figure}
\[\tableau{10\\9&8\\7&6\\&&5&4\\&&3\\&&2&1}\]
\caption{The composition tableau $S_{(2,1,2)*(2,2,1)}$.}\label{fig:Salpha}
\end{figure}

\subsection{Rule for column-strict quasisymmetric Schur functions}
Denote by $T^{\leq x}$ the restriction of $T$ to labels less than or equal to $x$.
We define a set $\mathcal{QO}(\alpha*\lambda)$ to be the set of composition fillings $T$ of any composition shape $\beta$ with $|\beta|=|\alpha|+|\lambda|$ satisfying 
\begin{enumerate}
\item the filling $T^{\leq |\alpha|}$  has shape $\gamma$ where $\gamma^+=\alpha$ and the entries $1,2,\ldots, |\alpha|$ occur in reading order, 
\item for each $i$, in $T^{\leq i}$ the length of the row containing $i$ is not equal to the length of any row below it,
\item if $i$ and $i+1$ are in the same row of $S_{\alpha*\lambda}$ then $i+1$ occurs strictly to the right of $i$ in $T$, and
\item if $i$ and $y$, $y<i$, are in the same column of $S_{\alpha*\lambda}$, then $i$ appears in a column weakly left of the column containing $y$ in $T$.
\end{enumerate}

To completely enumerate the elements of $\mathcal{QO}(\alpha*\lambda)$ it is convenient to use the conditions above to, label by label, create a tree with all possible placements of $1, \ldots, |\alpha|+|\lambda|$:

\begin{enumerate}
\item place the entries $1, \ldots, |\alpha|$ into the diagram of $\alpha$ in reading order (left to right, starting with the top row),  
\item for each $i$, $|\alpha|+1\leq i\leq |\alpha|+|\lambda|$, once $i-1$ has been placed, follow the rules for the placement of $i$ into the tableau:
\begin{enumerate}
\item If $i-1$ and $i$ are in the same row of $S_{\alpha*\lambda}$, $i$ must be placed in a column strictly to the right of the column containing $i-1$ such that once $i$ is placed at the end of a row, there is no row of the same length below it.  

\item If $i$ is in the same column as $y$, $y<i$, in $S_{\alpha*\lambda}$, then $i$ must be placed in a column weakly left of $y$ such that once $i$ is placed at the end of a row, there is no row of the same length below it.  In this case, allow for a row of length 0 between every pair of rows in the filling and $i$ can be placed in this row, provided there is no row of length 1 below it.

\end{enumerate}
\item keep track of each possible placement of $i$ by using a tree, as seen in \cref{fig:tree1},
\item if no placement of $i$  is possible, mark as a dead end and disregard, and
\item once $|\alpha|+|\lambda|$ has been placed, the elements of $\mathcal{QO}(\alpha*\lambda)$ are the leaves of the tree which are not dead ends.
\end{enumerate}

\begin{example}For $\alpha=(1,2,1)$ and $\lambda =(1,1)$, we get 
\[S_{\alpha*\lambda}=\tableau{6\\5\\&4\\&3&2\\&1},\]
and the elements of $\mathcal{QO}(\alpha*\lambda)$ are the leaves in the tree in \cref{fig:tree1}.  Then $\mathcal{CS}_{(1,2,1)}s_{(1,1)} = \mathcal{CS}_{(1,1,3,1)}+\mathcal{CS}_{(1,3,2)}+\mathcal{CS}_{(2,3,1)}+\mathcal{CS}_{(2,2,1,1)}+\mathcal{CS}_{(2,1,2,1)}+\mathcal{CS}_{(1,2,2,1)}+\mathcal{CS}_{(1,1,1,2,1)}.$

\end{example}

\begin{figure}
\begin{center}

\begin{tikzpicture}[level/.style={sibling distance=4cm},level distance=3cm]
\node (a){$\tableau{1\\2&3\\4}$}
	child{node (b){$\tableau{1\\2&3&5\\4}$}
		child {node  (e){$\tableau{1\\2&3&5\\4\\6}$}
		}
		child {node[left=.7cm] {$\tableau{1&6\\2&3&5\\4}$}
		}
		child {node[left=2.2cm]{$\tableau{1\\2&3&5\\4&6}$}
		}
	}
	child{node[left=.2cm] (d){$\tableau{1\\2&3\\4\\5}$}
		child{node (h){$\tableau{1\\2&3\\4\\5\\6}$}
		}
	}
	child{node[left=.2cm] (c){$\tableau{1\\2&3\\4&5}$}
		child{node[right=1cm]  (f){$\tableau{1\\6\\2&3\\4&5}$}
		}
		child{node  (g){$\tableau{1\\2&3\\6\\4&5}$}
		}
		child{node[left=.6cm] {$\tableau{1\\2&3\\4&5\\6}$}
		}
	};

\end{tikzpicture}
\end{center}
\caption{The tree generating elements of $\mathcal{QO}((1,2,1)*(1,1))$.}\label{fig:tree1}
\end{figure}



\begin{theorem} \label{thm:csrw} For $\alpha, \beta$ compositions and $\lambda$ a partition, let $A_{\alpha,\lambda}^\beta = |\mathcal{QO}(\alpha*\lambda, \beta)|$ where $\mathcal{QO}(\alpha*\lambda,\beta)$ is the subset of $\mathcal{QO}(\alpha*\lambda)$ of fillings with shape $\beta$.  Then  $A_{\alpha,\lambda}^\beta = B_{\alpha,\lambda}^\beta$ and \[\mathcal{CS}_\alpha(X) s_\lambda(X) = \sum_{\beta} A_{\alpha,\lambda}^\beta \mathcal{CS}_\beta(X).\] 

\end{theorem}

\begin{proof}  We define a function $f:\mathcal{QO}(\alpha*\lambda,\beta)\rightarrow LR(\beta/\alpha,\lambda)$ by replacing each label in $T\in \mathcal{QO}(\alpha*\lambda,\beta)$ by $0$ if $i$ is in $\alpha$ in $S_{\alpha*\lambda}$ and by $j$ if $i$ is in $\lambda_j$ in $S_{\alpha*\lambda}$ as seen in \cref{ex:f}. 

Let $T\in \mathcal{QO}(\alpha*\lambda,\beta)$.  By construction $f(T)$ has shape $\beta/\alpha$ and content $\lambda$, and rows weakly increase from left to right.  Since labels in the same row of $S_{\alpha*\lambda}$ cannot be in the same column of $T$, there are no repeated entries in columns in $f(T)$, except possibly 0's.  

Consider a type A triple in $f(T)$.  The triple has entries $a,b,c$ and the corresponding triple in $T$ has entries $a',b',c'$ as seen in \cref{fig:abtriples} where either $a$ or $b$ is the largest entry in the triple in $f(T)$.  Suppose first that $a$ is the largest entry.  Since $a$ and $b$ are in the same column, $a>b$ and since the rows of $f(T)$ are weakly increasing, we have $a>b\geq c$, so the triple condition is satisfied in this case.  Suppose next that $b>a$. Then in $T$, $b'>a'$ Thus, in $T^{\leq b'}$ the row containing $b'$ is the same length as the row containing $a'$, which is impossible since $T\in \mathcal{QO}(\alpha*\lambda,\beta)$.  A similar argument shows that all type B triples in $f(T)$ satisfy the triple condition.


Finally, we must show that $w_{col}(f(T))$ is a lattice word.  Let $1\leq i<\ell(\lambda)$.  In $T$, entries $x>y$ which are in the same column of $S_{\alpha*\lambda}$ appear with $x$ weakly left of $y$.  So in $T$ it is impossible to have more entries from row $i+1$ of $\lambda$ in $S_{\alpha*\lambda}$ than row $i$ when reading in column reading order.  Thus, it is not possible to have more $i+1$'s in a prefix than $i$'s.
Therefore $f(T) \in LR(\beta/\alpha,\lambda)$.

Define $g:LR(\beta/\alpha,\lambda) \rightarrow \mathcal{QO}(\alpha*\lambda,\beta)$ by $g(F)$ is the composition filling obtained by replacing each $i$ in $F$, $1\leq i\leq \ell(\lambda)$, from left to right by the entries in row $i$ of $\lambda$ in $S_{\alpha*\lambda}$, smallest entry to largest and replacing 0's from left to right starting in the top row with $1,2,\ldots,|\alpha|$.

Let $F\in LR(\beta/\alpha,\lambda)$.  We show that $g(F) \in \mathcal{QO}(\alpha*\lambda,\beta)$.  First note $g(F)^{\leq |\alpha|}$ has shape $\gamma$ where $\gamma^+ = \alpha$ since $F$ has shape $\beta /\alpha$.  The entries in $g(F)^{\leq |\alpha|}$ occur in reading order by definition of $g$.  

Next, suppose there is a an $i$ in row $j$ such that there exists a row $k$, $k<j$, with the same length as row $j$ in $g(F)^{\leq i}$.  Suppose $i$ occurs in column $x$ in $g(F)$.  Then in $F$, $F(j,x)>F(k,x)$, since otherwise, in $g(F)^{\leq i}$, cell $(k,x)$ would be empty.  Further, in $F$ row $j$ must be longer than row $k$, otherwise $F(k,x+1)<F(j,x)$ since $F\in LR(\beta/\alpha,\lambda)$ and thus satisfies the triple rules.  If $F(k,x+1)<F(j,x)$, then there is an entry in cell $(k,x+1)$ in $g(F)^{\leq i}$ and row $k$ is longer than row $j$.  Since row $j$ is longer than row $k$, the entries $F(j,x-1), F(j,x),$ and $F(k,x)$ form a type A triple.  Thus $F(j,x-1)>F(k,x)$ since $F(j,x)>F(k,x)$.  Further, $F(j,x-1)>F(k,x-1)$, and thus there exists some $y<x$, possibly $y=1$, such that $F(j,y)>F(k,y)\geq F(j,y-1)$, violating the type A triple rule. Thus, in $g(F)^{\leq i}$ there must be no rows below the row containing $i$ of the same length.

Now suppose $i$ and $i+1$ occur in the same row of $S_{\alpha*\lambda}$ for some $i>|\alpha|$.  Then, in $g(F)^{\leq i+1}$, $i+1$ occurs strictly to the right of $i$ since in $F$ the corresponding cells have the same label and hence cannot appear in the same column of $\beta$.  

Next suppose $i$ and $j$ occur in the same column of $S_{\alpha*\lambda}$ with $j<i$.  Suppose $i$ appears in a column strictly right of the column containing $j$ in $g(F)$.  If $i$ is in row $x$ of $\lambda$ in $S_{\alpha*\lambda}$ and $j$ is in row $m$ with both entries in column $z$, then there are at most $z-1$ occurrences of $m$ in $w_{col}(F)$ preceding the $z$th occurrence of $x$.  But this is impossible since $w_{col}(F)$ is a lattice word.  Thus $i$ appears in a column weakly left of $j$ in $g(F)$.  Therefore, $g(F) \in \mathcal{QO}(\alpha*\lambda, \beta)$.  




We show that $(g\circ f)(T)=T$ for all $T\in \mathcal{QO}(\alpha*\lambda,\beta)$ and $(f\circ g)(F)=F$ for all $F \in LR(\beta/\alpha,\lambda)$.  Given $T\in \mathcal{QO}(\alpha*\lambda,\beta)$, note that entries in $T$ corresponding to the entries in row $i$ in $\lambda$ in $S_{\alpha*\lambda}$ are in increasing order from left to right in $T$ with no two entries in the same row of $\lambda$ occurring in the same column of $T$.  This is sufficient to establish that $(g\circ f)(T) = T$. On the other hand, given $F \in LR(\beta/\alpha, \lambda)$, the labels in row $i$ of $\lambda$ in $S_{\alpha*\lambda}$ are arranged in $g(F)$ in increasing order from left to right in the cells of $F$ labeled with $i$.  In $(f\circ g)(F)$, the labels of $g(F)$ in row $i$ of $\lambda$ in $S_{\alpha*\lambda}$ are replaced by $i$ and thus $(f\circ g)(F) = F$.  Therefore, $g = f^{-1}$ and $A_{\alpha,\lambda}^\beta = B_{\alpha,\lambda}^\beta$.
\end{proof}  

\begin{example}\label{ex:f}
When $\alpha=(1,2,1)$, $\lambda=(2,2)$, then 
we see the result of applying $f$ to $T\in \mathcal{QO}(\alpha*\lambda)$ in \cref{fig:func}.
\begin{figure}
\[S_{\alpha*\lambda} = \tableau{8&7\\6&5\\&&4\\&&3&2\\&&1}\qquad T=\tableau{1\\2&3&6\\4&8\\5\\7} \qquad f(T) = \tableau{0\\0&0&1\\0&2\\1\\2}\]

\caption{The result of $f$ when applied to the tableau $T\in \mathcal{QO}((1,2,1)*(2,2))$.}\label{fig:func}
\end{figure}
\end{example}



\subsection{Rule for row-strict quasisymmetric Schur functions}\label{sec:RWRS}

We now present an analogous rule for $R_\alpha\cdot s_\lambda$ using row-strict composition fillings and row-strict Littlewood-Richardson composition tableaux.  

Define the set $\mathcal{RO}(\alpha*\lambda)$ to be the set of composition fillings $T$ satisfying 
\begin{enumerate}
\item the filling $T^{\leq|\alpha|}$ has shape $\gamma$ where $\gamma^+=\alpha$ and the entries $1,2,\ldots, |\alpha|$ occur in reading order,
\item for each $i$, the length of the row containing $i$ in $T^{\leq i}$ is not equal to the length of any row below it, 
\item if $i$ and $i+1$ are in the same row in $S_{\alpha*\lambda}$ then $i+1$ is weakly left of $i$ in $T$, and
\item if $i>j$ and $i,j$ are in the same column of $S_{\alpha*\lambda}$ then $i$ is strictly right of $j$ in $T$.
\end{enumerate}

As before, these conditions can easily be used to construct a tree whose leaves are the members of $\mathcal{RO}(\alpha*\lambda)$ as seen in \cref{fig:rstree}. 
\begin{figure}
\begin{center}

\begin{tikzpicture}[level/.style={sibling distance=4cm},level distance=3cm]
\node (a){$\tableau{1\\2&3\\4}$}
	child{node (b){$\tableau{1\\2&3&5\\4}$}
		child {node [left=.5cm]{$\tableau{1\\2&3&5&6\\4}$}
		}
	}
	child{node (d){$\tableau{1\\2&3\\4\\5}$}
		child{node [right=.25cm]{$\tableau{1\\2&3&6\\4\\5}$}
		}
		child{node[left=.1cm] {$\tableau{1\\2&3\\4&6\\5}$}
		}
		child{node [left=1.4cm]{$\tableau{1\\2&3\\4\\5&6}$}
		}
	}
	child{node (c){$\tableau{1\\2&3\\4&5}$}
		child{node[right=1.5cm] {$\tableau{1\\2&3\\4&5&6}$}
		}
		child{node[right=.8cm] {$\tableau{1\\2&3&6\\4&5}$}
		}
	};

\end{tikzpicture}
\end{center}
\caption{The tree generating elements of $\mathcal{RO}((1,2,1)*(1,1))$}\label{fig:rstree}
\end{figure}

\begin{theorem} \label{thm:rsrw}
Let $\lambda$ be a partition and $\alpha$ a composition.  Let $\mathcal{RO}(\alpha*\lambda,\beta)$ be the subset of $\mathcal{RO}(\alpha*\lambda)$ consisting of only those fillings of shape $\beta$.  Let $C_{\alpha,\lambda}^\beta=|\mathcal{RO}(\alpha*\lambda, \beta)|$.  Then $C_{\alpha,\lambda}^\beta = D_{\alpha,\lambda}^\beta$ and \[\mathcal{RS}_\alpha\cdot s_\lambda = \sum_\beta C_{\alpha,\lambda}^\beta \mathcal{RS}_\beta.\]

\end{theorem}

The proof of \cref{thm:rsrw} is similar to that of \cref{thm:csrw} and we will state the bijections while omitting the details.  Define $h:\mathcal{RO}(\alpha*\lambda,\beta)\rightarrow RSLR(\beta/\alpha,\lambda)$ by replacing each label in $T\in\mathcal{RO}(\alpha*\lambda,\beta)$ as follows.  If $i$ is in $\alpha$ in $S_{\alpha*\lambda}$, place a $0$ in $h(T)$ in the location of $i$ in $T$.  If $i$ is in row $k$ of $\lambda$ in $S_{\alpha*\lambda}$, place a $k$ in $h(T)$ in the location of $i$ in $T$.  Similarly, we define $p:RSLR(\beta/\alpha,\lambda)\rightarrow \mathcal{RO}(\alpha*\lambda,\beta)$ by replacing the 0's in $F\in RSLR(\beta/\alpha,\lambda)$ from left to right starting with the top row with the labels $1,2,\ldots,|\alpha|$ and for $1\leq i\leq \ell(\lambda)$ replace all $i$'s from right to left, down each column, with the labels in row $i$ of $\lambda$ in $S_{\alpha*\lambda}$ starting from the smallest label to the largest.  It is straightforward to show that $h$ and $p$ are inverse functions.  



\acknowledgements{The author would like to thank Sarah Mason for suggesting this project.}

 \printbibliography



\end{document}
